package com.leetCode.StringDemo;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class FindSubstringDemo {
    public static void main(String[] args) {
        System.out.println(findSubstring1("barfoofoobarthefoobarman",new String[]{"bar","foo","the"}));
    }

    /**
     * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
     *
     * s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
     *
     * 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。
     * "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
     * 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
     *
     * 示例 1：
     *
     * 输入：s = "barfoothefoobarman", words = ["foo","bar"]
     * 输出：[0,9]
     * 解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
     * 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
     * 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
     * 输出顺序无关紧要。返回 [9,0] 也是可以的。
     * 示例 2：
     *
     * 输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
     * 输出：[]
     * 解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
     * s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
     * 所以我们返回一个空数组。
     * 示例 3：
     *
     * 输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
     * 输出：[6,9,12]
     * 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
     * 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
     * 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
     * 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
     * 提示：
     *
     * 1 <= s.length <= 104
     * 1 <= words.length <= 5000
     * 1 <= words[i].length <= 30
     * words[i] 和 s 由小写英文字母组成
     * Related Topics
     * 哈希表
     * 字符串
     * 滑动窗口
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        if (s == null || words == null || words.length == 0){
            return new ArrayList<>();
        }
        List<String> wordList = Arrays.asList(words);
        char[] chars = s.toCharArray();
        List<Integer> result = new ArrayList<>();
        boolean next = false;
        int index = 0,count = 0;
        Integer firstIndex = null;
        while (index + 2 < chars.length){
            String str = "" + chars[index] + chars[index + 1] + chars[index + 2];
            if (wordList.contains(str)){
                if (!next){
                    firstIndex = index;
                }
                if (count == words.length - 1){
                    result.add(firstIndex);
                    firstIndex = null;
                    index = index + 2;
                    next = false;
                    count = -1;
                } else {
                    next = true;
                }
                count++;
            }
            index++;
        }
        return result;
    }

    public static List<Integer> findSubstring1(String s,String[] words){
        if (s == null || words == null || words.length == 0){
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();
        List<String> wordList = Stream.of(words).sorted().collect(Collectors.toList());
        List<String> tempList = new ArrayList<>(wordList.size());
        int stepLength = words[0].length();//每次截取多大的字符串
        int count = wordList.size();//截取多少次
        for (int i = 0;i < s.length();i++){
            if (i + count * stepLength <= s.length()){
                int everyCount = 0;
                int subIndex = i ;
                while (everyCount < count){
                    String str = s.substring(subIndex, subIndex + stepLength);
                    if (!wordList.contains(str)){
                        tempList.clear();
                        break;
                    }
                    tempList.add(str);
                    subIndex = subIndex + stepLength;
                    everyCount++;
                }
                List<String> sortTempList = tempList.stream().sorted().collect(Collectors.toList());
                if (wordList.equals(sortTempList)){
                    result.add(i);
                }
                tempList.clear();
            }
        }
        return result;
    }

    /**
     * 双map处理
     */
    public static List<Integer> findSubstring3(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        int wordNum = words.length;
        if (wordNum == 0) {
            return res;
        }
        int wordLen = words[0].length();
        //HashMap1 存所有单词
        HashMap<String, Integer> allWords = new HashMap<String, Integer>();
        for (String w : words) {
            int value = allWords.getOrDefault(w, 0);
            allWords.put(w, value + 1);
        }
        //遍历所有子串
        for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++) {
            //HashMap2 存当前扫描的字符串含有的单词
            HashMap<String, Integer> hasWords = new HashMap<String, Integer>();
            int num = 0;
            //判断该子串是否符合
            while (num < wordNum) {
                String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
                //判断该单词在 HashMap1 中
                if (allWords.containsKey(word)) {
                    int value = hasWords.getOrDefault(word, 0);
                    hasWords.put(word, value + 1);
                    //判断当前单词的 value 和 HashMap1 中该单词的 value
                    if (hasWords.get(word) > allWords.get(word)) {
                        break;
                    }
                } else {
                    break;
                }
                num++;
            }
            //判断是不是所有的单词都符合条件
            if (num == wordNum) {
                res.add(i);
            }
        }
        return res;
    }

    /**
     * 双Map处理
     */
    public static List<Integer> findSubstring4(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int wordNum = words.length;
        if (wordNum == 0){
            return res;
        }
        int wordLen = words[0].length();
        //HashMap1
        Map<String,Integer> allWords = new HashMap<>();
        for (String w : words){
            int value = allWords.getOrDefault(w, 0);
            allWords.put(w,value + 1);
        }
        //遍历子串
        for (int i = 0;i < s.length() - wordNum * wordLen + 1;i++){
            //HashMap2 存当前扫描的字符串含有的单词
            Map<String,Integer> hasWords = new HashMap<>();
            int num = 0;
            //判断该子串是否符合
            while (num < wordNum){
                String word = s.substring(i + num * wordLen,i + (num + 1) * wordLen);
                //判断该单词在HashMap1中
                if (allWords.containsKey(word)){
                    int value = hasWords.getOrDefault(word, 0);
                    hasWords.put(word,value + 1);
                    //判断当前单词的value 和 HashMap1中该单词的 value
                    if (hasWords.get(word) > allWords.get(word)){
                        break;
                    }
                } else {
                    break;
                }
                num++;
            }
            //判断是不是所有单词都符合条件
            if (num == wordNum){
                res.add(i);
            }
        }
        return res;
    }

    /**
     * 滑动窗口解决
     */
    public static List<Integer> findSubstring5(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        int wordNum = words.length;
        if (wordNum == 0) {
            return res;
        }
        int wordLen = words[0].length();
        HashMap<String, Integer> allWords = new HashMap<String, Integer>();
        for (String w : words) {
            int value = allWords.getOrDefault(w, 0);
            allWords.put(w, value + 1);
        }
        //将所有移动分成 wordLen 类情况
        for (int j = 0; j < wordLen; j++) {
            HashMap<String, Integer> hasWords = new HashMap<String, Integer>();
            int num = 0; //记录当前 HashMap2（这里的 hasWords 变量）中有多少个单词
            //每次移动一个单词长度
            for (int i = j; i < s.length() - wordNum * wordLen + 1; i = i + wordLen) {
                boolean hasRemoved = false; //防止情况三移除后，情况一继续移除
                while (num < wordNum) {
                    String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
                    if (allWords.containsKey(word)) {
                        int value = hasWords.getOrDefault(word, 0);
                        hasWords.put(word, value + 1);
                        //出现情况三，遇到了符合的单词，但是次数超了
                        if (hasWords.get(word) > allWords.get(word)) {
                            // hasWords.put(word, value);
                            hasRemoved = true;
                            int removeNum = 0;
                            //一直移除单词，直到次数符合了
                            while (hasWords.get(word) > allWords.get(word)) {
                                String firstWord = s.substring(i + removeNum * wordLen, i + (removeNum + 1) * wordLen);
                                int v = hasWords.get(firstWord);
                                hasWords.put(firstWord, v - 1);
                                removeNum++;
                            }
                            num = num - removeNum + 1; //加 1 是因为我们把当前单词加入到了 HashMap 2 中
                            i = i + (removeNum - 1) * wordLen; //这里依旧是考虑到了最外层的 for 循环，看情况二的解释
                            break;
                        }
                        //出现情况二，遇到了不匹配的单词，直接将 i 移动到该单词的后边（但其实这里
                        //只是移动到了出现问题单词的地方，因为最外层有 for 循环， i 还会移动一个单词
                        //然后刚好就移动到了单词后边）
                    } else {
                        hasWords.clear();
                        i = i + num * wordLen;
                        num = 0;
                        break;
                    }
                    num++;
                }
                if (num == wordNum) {
                    res.add(i);

                }
                //出现情况一，子串完全匹配，我们将上一个子串的第一个单词从 HashMap2 中移除
                if (num > 0 && !hasRemoved) {
                    String firstWord = s.substring(i, i + wordLen);
                    int v = hasWords.get(firstWord);
                    hasWords.put(firstWord, v - 1);
                    num = num - 1;
                }

            }

        }
        return res;
    }

    /**
     * 滑动窗口解决
     */
    public static List<Integer> findSubstring6(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        int m = words.length, n = words[0].length(), ls = s.length();
        for (int i = 0; i < n; i++) {
            if (i + m * n > ls) {
                break;
            }
            Map<String, Integer> differ = new HashMap<String, Integer>();
            for (int j = 0; j < m; j++) {
                String word = s.substring(i + j * n, i + (j + 1) * n);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
            }
            for (String word : words) {
                differ.put(word, differ.getOrDefault(word, 0) - 1);
                if (differ.get(word) == 0) {
                    differ.remove(word);
                }
            }
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    String word = s.substring(start + (m - 1) * n, start + m * n);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                    word = s.substring(start - n, start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                }
                if (differ.isEmpty()) {
                    res.add(start);
                }
            }
        }
        return res;
    }
}
